package com.study._1_linked_lister;

public class Main {

    /**
     * 1.单链表反转 √
     * 2.链表中环
     * 2.1 给一个单链表，判断其中是否有环的存在；√
     * 2.2 如果存在环，找出环的入口点；
     * 2.3 如果存在环，求出环上节点的个数；
     * 2.4 如果存在环，求出链表的长度；
     * 2.5 如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
     * 2.6（扩展）如何判断两个无环链表是否相交；
     * 2.7（扩展）如果相交，求出第一个相交的节点；
     * 3.两个有序的链表合 √
     * 4.删除链表倒数第 n 个结点 √
     * 5.求链表的中间结点 √
     */
    public static void main(String[] args) {
        // 1
//        LinkedNode linkedNode = LinkedUtils.build(1,2,3,4,5,6,7,8,9,10,11);
//        LinkedUtils.print(linkedNode);
//        LinkedNode revert = revert(linkedNode);
//        LinkedUtils.print(revert);

        //2.1
//        LinkedNode linkedNode = LinkedUtils.build(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
//        LinkedNode lastNode = LinkedUtils.findLastNode(linkedNode);
//        lastNode.next = linkedNode;
//        boolean hasRing = hasRing(linkedNode);
//        System.out.println(hasRing);

        //2.2
        //2.3
        //2.4
        LinkedNode linkedNode = LinkedUtils.build(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13);
        LinkedNode lastNode = LinkedUtils.findLastNode(linkedNode);
        lastNode.next = linkedNode;
        lastNode.next = linkedNode.next.next;
        LinkedNode ringStartNode = findRingStartNode(linkedNode);
        System.out.println(ringStartNode == null ? null : ringStartNode.data);

        //2.5
        //这咋写  先算环的长度 再走一半?
        //或者快慢指针 快的转一圈 慢的就是最远节点?
//        LinkedNode linkedNode = LinkedUtils.build(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13);
//        LinkedNode lastNode = LinkedUtils.findLastNode(linkedNode);
//        lastNode.next = linkedNode;
//        LinkedNode farthestNode = findFarthestNode(linkedNode);
//        System.out.println(farthestNode == null ? null : farthestNode.data);


        //2.6
        //2.7
        // TODO: 2018/12/16 所有操作都在链表元素不重复的条件下,若重复应该要根据节点的地址做判断
        LinkedNode linked1 = LinkedUtils.build(1, 2, 3, 4, 5, 6, 7);
        LinkedNode linked2 = LinkedUtils.build(8, 9, 10);
        LinkedUtils.findLastNode(linked2).next = linked1.next.next.next;
        boolean hasIntersect = hasIntersect(linked1, linked2);
        System.out.println("hasIntersect : " + hasIntersect);

        // 3
//        LinkedNode linkedNode1 = LinkedUtils.build(1, 3, 5, 7, 8, 10, 12);
//        LinkedNode linkedNode2 = LinkedUtils.build(2, 4, 6, 9, 11);
//        LinkedUtils.print(linkedNode1);
//        LinkedUtils.print(linkedNode2);
//        LinkedNode result = merge(linkedNode1, linkedNode2);
//        LinkedUtils.print(result);

        // 4
//        LinkedNode linkedNode = LinkedUtils.build(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
//        LinkedUtils.print(linkedNode);
//        LinkedNode result = remove(linkedNode, 13);
//        LinkedUtils.print(result);

        // 5 中间节点要么是一个要么是两个
//        LinkedNode linkedNode = LinkedUtils.build(1);
//        LinkedUtils.print(linkedNode);
//        LinkedNode midNode = findMidNode(linkedNode);
//        LinkedUtils.print(midNode);
//        int[] pos = findMidNodePos(linkedNode);
//        System.out.println("pos : " + Arrays.toString(pos));
    }

    /**
     * 2.6（扩展）如何判断两个无环链表是否相交；
     * 2.7（扩展）如果相交，求出第一个相交的节点；
     */
    private static boolean hasIntersect(LinkedNode linked1, LinkedNode linked2) {
        //把一个链表 首尾相连变成环,  另一个链表做起点 就可以把问题转换为一个链表是否有环的问题
        LinkedNode lastNode = LinkedUtils.findLastNode(linked1);
        lastNode.next = linked1;

        boolean hasRing = hasRing(linked2);

        LinkedNode ringStartNode = findRingStartNode(linked2);
        System.out.println("第一个交点 : " + ringStartNode.data);

        //把环去掉
        lastNode.next = null;

        return hasRing;
    }

    /**
     * 2.5 如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
     */
    private static LinkedNode findFarthestNode(LinkedNode header) {
        if (!hasRing(header)) {
            return null;
        }

        LinkedNode slowNode = header;
        LinkedNode fastNode = header;

        do {
            System.out.println("slowNode : " + slowNode.data);
            System.out.println("fastNode : " + fastNode.data);
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        while (!(header.data == fastNode.data || header.next.data == fastNode.data));

        return slowNode;
    }

    /**
     * 2.2 如果存在环，找出环的入口点；
     * 2.3 如果存在环，求出环上节点的个数；
     * 2.4 如果存在环，求出链表的长度；
     */
    static LinkedNode findRingStartNode(LinkedNode header) {
        // TODO: 2018/12/15 可以优化掉
        if (!hasRing(header)) {
            return null;
        }

        LinkedNode slow = header, faster = header;
        int firstMeetPos = 0;
        //第一次相遇
        while (slow.next != null && faster.next != null && faster.next.next != null) {
            slow = slow.next;
            faster = faster.next.next;
            firstMeetPos++;
            if (slow.data == faster.data) {
                break;
            }
        }


//        快慢指针 同时从环的一个点P出发 最后还是会在P点回合 所以 secondMeetPos为环的长度
        int ringLength = 0;
        while (slow.next != null && faster.next != null && faster.next.next != null) {
            slow = slow.next;
            faster = faster.next.next;
            ringLength++;
            if (slow.data == faster.data) {
                break;
            }
        }


//        System.out.println();
//        System.out.println("firstMeetPos : " + firstMeetPos);
        System.out.println("环上点的个数 : " + ringLength);


        // 链表总长度为 l =  非环部分长度 f + 环的长度 r                    (1)
        // 第一次相交, 慢指针走的长度为 sl = f + 慢指针在环中走的长度 s       (2)
        // 第一次相交, 快指针走的长度为 fl = f + r*n(快指针在相交前在环上的绕的圈数) + s  (3)
        // 且 fl = 2sl;                          (4)


        // 由 (2)(4)得 :
        //  fl = 2(f+s)     (5)

        // 由 (4)(5)得
        // 2(f+s) = f + rn + s
        //得 f = rn - s  =>  f = (r-1)n + (r-s)
        // 所以设置两个指针 分别同时从起点和交点处出发,最终会在环的入口处相交

        int linkedLength = ringLength;
        while (header.data != slow.data) {
            linkedLength++;
            header = header.next;
            slow = slow.next;
        }

        System.out.println("链表的长度 : " + linkedLength);

        return header;
    }


    /**
     * 2.1 给一个单链表，判断其中是否有环的存在
     */
    static boolean hasRing(LinkedNode rootNode) {
        if (rootNode == null) {
            return false;
        }
        LinkedNode slowNode = rootNode;
        LinkedNode fastNode = rootNode;
//        System.out.print(slowNode.data + ", ");
        while (slowNode.next != null && fastNode.next != null && fastNode.next.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
//            System.out.print(slowNode.data + ", ");
            if (slowNode.data == fastNode.data) {
                return true;
            }
        }
        return false;
    }


    /**
     * 5.求链表的中间结点
     */
    static LinkedNode findMidNode(LinkedNode root) {
        if (root == null || root.next == null) {
            return root;
        }
        LinkedNode header = root;
        LinkedNode mid = root;

        while (header.next.next != null) {
            header = header.next.next;
            mid = mid.next;

            if (header.next == null) {
                return mid;
            }
        }
//        mid = mid.next;
        return mid;
    }

    /**
     * 5.求链表的中间结点
     */
    static int[] findMidNodePos(LinkedNode root) {
        if (root == null) {
            return new int[]{-1};
        }
        if (root.next == null) {
            return new int[]{0};
        }
        LinkedNode header = root;
        LinkedNode mid = root;
        int midPos = 0;
        while (header.next.next != null) {
            header = header.next.next;
            mid = mid.next;
            midPos++;
            if (header.next == null) {
                return new int[]{midPos};
            }
        }
        return new int[]{midPos, midPos + 1};
    }


    /**
     * 4.删除链表倒数第 n 个结点
     */
    static LinkedNode remove(LinkedNode root, int posFromLast) {
        int targetPos = 0;

        LinkedNode target = root;
        LinkedNode header = root;

        while (targetPos < posFromLast + 1) {
            if (root == null) {
                if (targetPos == posFromLast) {
                    //刚好够长
                    target = target.next;
                }
                //长度不够
                return target;
            }
            root = root.next;
            ++targetPos;
        }

        while (root != null) {
            root = root.next;
            target = target.next;
        }
        target.next = target.next.next;
        return header;
    }


    /**
     * 3.两个有序的链表合并
     */
    static LinkedNode merge(LinkedNode l1, LinkedNode l2) {
        LinkedNode root;
        LinkedNode header;
        if (l1.data <= l2.data) {
            root = l1;
            l1 = l1.next;
        } else {
            root = l2;
            l2 = l2.next;
        }
        header = root;

        while (l1 != null && l2 != null) {
            if (l1.data < l2.data) {
                root.next = l1;
                l1 = l1.next;
            } else {
                root.next = l2;
                l2 = l2.next;
            }
            root = root.next;
        }

        if (l1 == null) {
            root.next = l2;
        } else {
            root.next = l1;
        }

        return header;
    }

    /**
     * 1.单链表反转 √
     */
    static LinkedNode revert(LinkedNode rootNode) {
        if (rootNode == null) {
            return null;
        }
        LinkedNode header = rootNode.next;
        rootNode.next = null;
        while (header != null) {
            LinkedNode temp = header;
            header = header.next;
            temp.next = rootNode;
            rootNode = temp;
        }
        return rootNode;

    }

}
